This application relates to telecommunication systems having frame scheduling schemes for simultaneous circuit-switched and packet-based communication.
Traditional communication networks often have a hierarchical architecture. A user accesses the network via a source node and is routed through dedicated equipment in the network to a destination node. For example, a wireless, cellular telephone user originates a communication session by dialing the telephone number of a desired destination. The call from the users terminal is received in a base transceiver station (BTS), which passes the call to other nodes in the wireless network and perhaps through a wireline network to the destination, which may be a terminal in either the wireless or wireline networks. It will be appreciated that the terminals may include voice devices like telephones and data devices like personal computers (PCs), personal digital assistants (PDAs), and other devices capable of transmitting data packets.
Ad-hoc communication networks enable terminals to form direct connections without the assistance of an intervening communication network. Wireless systems that support ad-hoc connections should provide direct communication among any radio units that are in range of one another. Such ad-hoc communication sessions can use the unlicensed industrial, scientific, and medical (ISM) band at 2400 MHz that has been opened for commercial applications, and many commercially available products can provide wireless communications in these bands.
The use of the ISM band is restricted in the United States by Part 15 of the rules of the Federal Communications Commission (FCC) and in Europe by ETS 300 328 of the European Telecommunication Standards Institute (ETSI). Other countries apply similar rules. Briefly stated, the U.S. rules require a user to spread its transmitted power over the frequency band in order to minimize the chance of interference with other users.
Such spreading can be achieved by two techniques known in the art of spread spectrum communication systems. In the frequency-hopping technique, the transmitter emits a carrier signal that is modulated in a conventional way by the information to be sent, and the frequency of the carrier signal is changed (hopped) according to a predetermined pattern that is known to the receiver. GSM-type cellular telephone systems are examples of frequency-hopping communication systems. In the direct-sequence technique, the carrier signal has a fixed frequency and is modulated in a conventional way by a combination of binary data to be sent and a noise-like, higher-bit-rate, binary sequence that is known to the receiver. CDMA-type cellular telephone systems are examples of direct-sequence spread spectrum communication systems.
A BLUETOOTH™ wireless communication system operates in the ISM band at 2400 MHz using a fast frequency-hopping scheme to minimize interference with non-BLUETOOTH™ sources. The frequency-hopping occurs nominally at 1,600 hops per second, and the system has 79 possible channels (carriers), with a typical channel spacing of 1 MHz. A BLUETOOTH™ wireless network can carry both synchronous traffic, e.g., voice conversations, and asynchronous traffic, e.g., data packets that follow the Internet protocol (IP). Two or more BLUETOOTH™ (BT) units sharing the same channel form a piconet, two of which are depicted in FIGS. 1A, 1B. Each BT unit in a piconet may perform the functions of either a master or slave, and within each piconet, there is only one master and up to seven active slaves. In FIGS. 1A, 1B, the master unit is indicated by hatching and the slave units are indicated by no hatching. All slave units in a piconet synchronize themselves to the master unit's clock cycle and hopping sequence.
Aspects of BLUETOOTH™ systems are disclosed in this application and in J. Haartsen, “Bluetooth—The Universal Radio Interface for ad hoc, Wireless Connectivity”, Ericsson Review no. 3, pp. 110-117 (1998); and M. Frodigh et al., “Wireless ad hoc Networking—The Art of Networking without a Network”, Ericsson Review no. 4, pp. 248-263 (2000), both of which are currently available on the World Wide Web. Aspects of BLUETOOTH™ and other communication systems are described in U.S. patent application Ser. No. 09/454,758 filed on Dec. 6, 1999, by P. Johansson for “System and Method for Scheduling Communication Sessions in an ad-hoc Network”; Ser. No. 09/455,172 filed on Dec. 6, 1999, entitled “Batched Fair Exhaustive Polling Scheduler”; Ser. No. 09/834,911 filed on Apr. 16, 2001, by F. Alriksson et al. for “Rendezvous Point Interpiconet Scheduling (RIPS)”; Ser. No. 09/852,114 filed on May 9, 2001, by J. Haartsen for “Method and Apparatus for Managing Traffic Flows”; and Ser. No. 09/952,707 filed on Sep. 14, 2001, by J. Sorensen for “Administrative Domains for Personal Area Networks”. Further information about BLUETOOTH™ systems is available at http://www.bluetooth.org.
The specifications of BLUETOOTH™ communication systems support both point-to-point and point-to-multipoint network connections. Referring again to FIG. 1A, piconet 110 is a point-to-point piconet, with a master node 112 and a single slave node 114. In FIG. 1B, piconet 130 is a point-to-multipoint piconet, with a master node 132 and seven slave nodes 134-146.
Two or more piconets can be interconnected, forming what is called a scatternet. Since each piconet includes a master or supervisory unit that generally has its own clock timing and frequency hopping scheme, piconets interconnected in a scatternet are generally independent and unsynchronized. A node that is the interconnection point between two piconets is a BT unit that is a member of both piconets. A BT unit can be a slave unit in any number of interconnected piconets and a master in only other interconnected piconet. This is depicted in FIG. 2, which shows a scatternet comprising twelve interconnected piconets 1-12. BT units M1, M3, M4, M6, M7, M9, M11, M12 act as only master units in their respective piconets 1, 3, 4, 6, 7, 9, 11, 12 and are depicted as hatched circles. BT units M2, M5, M8 act as master units in their respective piconets 2, 5, 8 and as slave units in only one other piconet (piconets 1, 7, 9, respectively) and are depicted as half-darkened circles. BT unit M10 acts as a master unit in its respective piconet 10 and as a slave unit in two other piconets 11, 12 and is depicted as a one-third-darkened circle. In FIG. 2, circles indicating slave units are similarly divided to illustrate the number of piconets to which the respective unit belongs.
A BLUETOOTH™ system provides full-duplex communication by slotted time division duplex (TDD), in which each slot is 0.625 millisecond (ms) long. The time slots are numbered sequentially using numbers in a very large range (i.e., cycling through a range of 227). Master-to-slave transmission starts in an even-numbered time slot and slave-to-master transmission starts in an odd-numbered time slot. An even-numbered time slot and its subsequent odd-numbered time slot (i.e., a master-to-slave time slot and a slave-to-master time slot, except when packets needing multiple slots are used) together are called a frame. There is no direct transmission between slaves in a BLUETOOTH™ piconet; all communication takes place between master and slave nodes.
Communication within a piconet is organized such that the master polls each slave according to a polling scheme. A slave typically transmits after being polled by the master, with minor exceptions described below. The slave starts its transmission in the slave-to-master time slot immediately following the packet (slot) received from the master. The master may or may not include data in the packet used to poll a slave. An exception to this principle is that when a slave has an established synchronous connection-oriented (SCO) link, which is described further below, the slave may continue to transmit in the slave-to-master time slot that has been reserved by the master, even if it is not explicitly polled by the master in the preceding master-to-slave time slot.
A globally unique, 48-bit address according to the IEEE 802 specification is assigned to each BT unit when it is manufactured, and this address, called the Bluetooth Device Address (BD_ADDR), is never changed. In addition, the master BT unit of a piconet assigns a local Active Member Address (AM_ADDR) to each active member of the piconet. The AM_ADDR is a three-bit media-access-control (MAC) address assigned and cleared dynamically, and is unique only within that piconet. The master uses AM_ADDRs when polling slaves in a piconet, and when a slave transmits a packet to the master in response to a packet received from the master, the slave includes its own AM_ADDR in the packet header, not the master's AM_ADDR.
All data is transmitted as packets, which can carry both synchronous data on SCO links and asynchronous data like IP packets on asynchronous connection-less (ACL) links. SCO links support symmetrical, circuit-switched, point-to-point connections typically used for voice, and these links are defined on the frequency-hopping channel by reservation of pairs of consecutive (forward and reverse) slots, i.e., frames, at fixed intervals. ACL links support symmetrical or asymmetrical, packet-switched, point-to-multipoint connections typically used for bursty data transmissions. An acknowledgment and re-transmission scheme is used for ACL-link packets to ensure reliable transfer of data. Forward error correction (FEC) coding may also be used.
A standard format of a BLUETOOTH™ packet is illustrated in FIG. 3 and includes an access code, header, and payload, although some packets may use different formats. The access code is a 72-bit sequence that is derived from a master's identity by each slave in a piconet and is unique for the channel; every packet exchanged on a channel includes the respective access code. Receivers on a piconet compare the access code of a received packet to the expected access code, discarding the packet if the codes do not match. The AM_ADDR is located in the header, which is a 54-bit sequence that also includes various control parameters, e.g., a bit indicating an acknowledgment or a re-transmission request of the previous packet, and a header error check (HEC). The format of the payload, comprising 0-2745 bits, depends on the type of packet. The payload of a typical ACL packet includes a header, a data field, and a cyclic redundancy check (CRC); AUX1-type ACL packets have payloads arranged differently. The payload of a typical SCO packet includes only a data field. Besides ACL and SCO packets, there are hybrid packets that each include two data fields, one for synchronous data and one for asynchronous data. Packets in which the payload does not include a CRC are neither acknowledged nor re-transmitted.
The master unit of a piconet schedules the traffic in the piconet through its polling of the slave units. This is called intrapiconet scheduling in this application. In a scatternet, at least one BT unit is a member of more than one piconet, so scheduling the presence of this node, which may be called an interpiconet node, in its different piconets is a complex task in view of the need to handle circuit-switched (synchronous) data and packet-switched (asynchronous) data with varying packet sizes. This is called interpiconet scheduling in this application.
To schedule scatternet traffic efficiently, the BT units scheduling traffic within their respective piconets should consider the scheduling of traffic between the piconets in their polling of the slaves of their piconets. For instance, an intrapiconet scheduler in a master unit might not schedule an interpiconet node when the latter is active in another piconet and it might schedule the interpiconet node more often when the latter is again active in its piconet.
The complexity of such scheduling can easily overwhelm the processing resources available in the master units for performing the scheduling function. If a master unit's central processing unit (CPU) must deal with scheduling each individual packet, the CPU can become too heavily loaded by the necessarily large number of interrupts. In addition to scheduling transmission and reception, the scheduler must control paging for new piconet nodes, inquiry scans, and page scans, which are operations specified in BLUETOOTH™ communication systems that have counterparts in other communication systems.